#ifndef LIBACCENT_ALGORITHMS_ROTATE_HPP
#define LIBACCENT_ALGORITHMS_ROTATE_HPP

#include "accent/core.hpp"
#include "accent/algorithms/reverse.hpp"
#include <cassert>
#include <utility>

namespace accent
{
  template <typename ForwardRange>
  typename ForwardRange::position
    rotate(ForwardRange r, typename ForwardRange::position pivot);

  namespace detail
  {
    // FIXME: move this somewhere else
    template <typename Integer>
    Integer gcd(Integer a, Integer b)
    {
      for (;;) {
        if (b == 0)
          return a;
        a = a % b;
        if (a == 0)
          return b;
        b = b % a;
      }
    }

    template <typename ForwardRange>
    void swap_ranges(ForwardRange& r, ForwardRange& s)
    {
      while (!r.empty() && !s.empty()) {
        using std::swap;
        swap(r.front(), s.front());
        r.pop_front();
        s.pop_front();
      }
    }

    template <typename ForwardRange>
    typename ForwardRange::position
      do_rotate(ForwardRange r, typename ForwardRange::position pivot,
                forward_traversal_tag)
    {
      auto before = r.until(pivot), b0 = before;
      auto after = r.from(pivot), a0 = after;
      swap_ranges(before, after);
      // case 0: |1|2| -> |2|1| done
      if (before.empty() && after.empty())
        return pivot;
      // case 1: |1|2 3| -> |2|1,3|
      //          b  a          a'
      if (before.empty())
        return rotate(a0, after.front_position());
      // case 2: |1 2|3| -> |3,2|1|
      //           b  a       b'
      auto new_pivot = before.front_position();
      ::accent::rotate(r.from(new_pivot), pivot);
      return new_pivot;
    }

    template <typename BidirectionalRange>
    typename BidirectionalRange::position
      do_rotate(BidirectionalRange r,
                typename BidirectionalRange::position pivot,
                bidirectional_traversal_tag)
    {
      auto front = r.until(pivot);
      auto back = r.from(pivot);
      auto new_front = reverse_with_position(front, r.front_position());
      // position cannot be in back unless pivot == front, which we special-case
      reverse(back);
      return reverse_with_position(r, new_front);
    }

    template <typename RandomAccessRange>
    void rotate_cycle(RandomAccessRange range,
                      std::size_t jump, std::size_t offset)
    {
      auto size = range.size();
      auto temp = std::move(range[offset]);
      std::size_t target = 0;
      for (auto source = jump; source != 0;
           target = source, source = (source + jump) % size)
      {
        range[target + offset] = std::move(range[source + offset]);
      }
      range[target + offset] = std::move(temp);
    }

    template <typename RandomAccessRange>
    typename RandomAccessRange::position
      do_rotate(RandomAccessRange r,
                typename RandomAccessRange::position pivot,
                random_access_traversal_tag)
    {
      auto front_size = r.until(pivot).size();
      auto cycles = gcd(front_size, r.from(pivot).size());

      for (std::size_t offset = 0; offset < cycles; ++offset) {
        rotate_cycle(r, front_size, offset);
      }
      // Compute new position of first.
      r.skip_front(r.size() - front_size);
      return r.front_position();
    }

  }

  // rotate the range [front, ..., pivot-1, pivot, ..., back] to
  // [pivot, ..., back, front, ..., pivot-1]
  // returns the position of front in the result
  // if pivot is nothing, does nothing and returns nothing
  template <typename ForwardRange>
  typename ForwardRange::position
    rotate(ForwardRange r, typename ForwardRange::position pivot)
  {
    if (!pivot || pivot == r.front_position()) return pivot;

    return detail::do_rotate(r, pivot, typename ForwardRange::traversal());
  }

}

#endif
